Programmable logic devices (“PLDs”) are a well-known type of integrated circuit that can be programmed to perform specified logic functions. One type of PLD, the field programmable gate array (“FPGA”), typically includes an array of programmable tiles. These programmable tiles can include, for example, input/output blocks (“IOBs”), configurable logic blocks (“CLBs”), dedicated random access memory blocks (“BRAMs”), multipliers, digital signal processing blocks (“DSPs”), processors, clock managers, delay lock loops (“DLLs”), and so forth. Notably, as used herein, “include” and “including” mean including without limitation.
One such FPGA, the Xilinx Virtex® FPGA, is described in detail in pages 3-75 through 3-96 of the Xilinx 2000 Data Book entitled “The Programmable Logic Data Book 2000” (hereinafter referred to as “the Xilinx Data Book”), published April, 2000, available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124. (Xilinx, Inc., owner of the copyright, has no objection to copying these and other pages referenced herein but otherwise reserves all copyright rights whatsoever.)
Another type of PLD is the Complex Programmable Logic Device (“CPLD”). A CPLD includes two or more “function blocks” connected together and to input/output (“I/O”) resources by an interconnect switch matrix. Each function block of the CPLD includes a two-level AND/OR structure similar to those used in Programmable Logic Arrays (“PLAs”) and Programmable Array Logic (“PAL”) devices. Other PLDs are programmed by applying a processing layer, such as a metal layer, that programmably interconnects the various elements on the device. These PLDs are known as mask programmable devices. PLDs can also be implemented in other ways, for example, using fuse or antifuse technology. The terms “PLD” and “programmable logic device” include but are not limited to these exemplary devices, as well as encompassing devices that are only partially programmable.
For purposes of clarity, FPGAs are described below though other types of PLDs may be used. FPGAs may include one or more embedded microprocessors. For example, a microprocessor may be located in an area reserved for it, generally referred to as a “processor block.”
A problem with parallelizing a signal processing algorithm over multiple pipelines, such as may be implemented in a multi-processor or multi-threaded system, is data dependencies associated with preservation of the order of execution of data. Conventionally, state and feedback loops in such systems cause execution to stall or wait until data becomes available to preserve the order of execution. Particularly, with respect to stateful resources, such as state variables, they may only be modified one user at a time to preserve the order of execution. Thus, only one thread or processor may use such resources at a time.
Heretofore, to preserve the order of execution, resource allocation tables were used. These tables consume a significant amount of circuitry and were conventionally implemented with software primitives for “score boarding.” Software primitives used for sharing stateful resources are generally “critical sections” and “semaphores” containing code that allows only one processor or thread to execute at a time.
Accordingly, it would be desirable and useful to provide means to share resources with parallel processing that uses less circuitry than the above-mentioned examples.